#include <iostream>
#include <vector>
#include <stack>
#include <unordered_map>
using namespace std;
class Solution
{
public:
    /**
     * @brief
     * 1 <= expression.length <= 2000
     *
     * @param expression
     * @return int
     */
    unordered_map<string, int> map; //变量映射
    unordered_map<int, int> index;  //括号匹配

    // getNum处理的是未去除括号的表达式或变量，数字，并取值
    int getNum(const string &s, int start, int end)
    {
        if (s[start] == '(')
        {
            // DFS需要去掉括号
            return DFS(s, start + 1, end - 1);
        }
        else if (isalpha(s[start]))
        {
            return map[s.substr(start, end - start + 1)];
        }
        return stoi(s.substr(start, end - start + 1));
    }

    pair<int, int> getNumbers(const string &str, int start, int end)
    { //为add和mult设计的getNum
        int pos = start;
        //一共两个元素，开头为'('就找右括号的下一位为分隔，否则找子字符串的第一个空格为分隔
        if (str[start] == '(')
        {
            pos = index[start] + 1 - start;
        }
        else
        {
            pos = str.substr(start, end - start + 1).find_first_of(' ');
        }
        return {getNum(str, start, start + pos - 1), getNum(str, start + pos + 1, end)};
    }
    /**
     * @brief 去除括号和add的表达式
     *
     * @param str
     * @param start
     * @param end
     * @return int
     */
    int add(const string &str, int start, int end)
    {
        auto res = getNumbers(str, start, end);
        return res.first + res.second;
    }

    /**
     * @brief 去除括号和mult的表达式
     *
     * @param str
     * @param start
     * @param end
     * @return int
     */
    int mult(const string &str, int start, int end)
    {
        auto res = getNumbers(str, start, end);
        return res.first * res.second;
    }

    /**
     * @brief 去除括号和let的表达式
     *
     * @param s
     * @param start
     * @param end
     * @return int
     */
    int let(const string &s, int start, int end)
    {
        string key;
        int left = start;
        bool flag = 0; //用于计算当前字符串为 key还是value
        for (int i = start; i <= end; ++i)
        {
            if (s[left] == '(')
            { //同样，如果首字符为'('，找右括号，否则根据空格来分割
                int right = index[left];
                if (right != end)
                {
                    map[key] = getNum(s, left, right);
                }
                else
                {
                    return getNum(s, left, right);
                }
                flag = 1 - flag;
                left = right + 2; //下一个的首字符
                i = right + 1;    // i走到下一个字符前的空格处
            }
            else if (!flag && s[i] == ' ')
            {
                key = s.substr(left, i - left);
                left = i + 1;
                flag = 1 - flag;
            }
            else if (flag && s[i] == ' ')
            {
                map[key] = getNum(s, left, i - 1);
                flag = 1 - flag;
                left = i + 1;
            }
        }
        return getNum(s, left, end); //如果最后expr不是括号表达式，那么最后留下来的字符串即为返回
    }

    int DFS(const string &s, int start, int end)
    { // DFS处理的为 已经去除括号的表达式
        if (s[start] == 'l')
        { //进入let会更新map的映射，离开let应该还原 原版本的map
            unordered_map<string, int> temp = map;
            int res = let(s, start + 4, end);
            map = temp;
            return res;
        }
        else if (s[start] == 'a')
        {
            return add(s, start + 4, end);
        }
        else
        {
            return mult(s, start + 5, end);
        }
    }

    int evaluate(string expression)
    {
        //利用栈来找到并记录每对括号的位置
        stack<int> stk;
        for (int i = 0; i < expression.size(); ++i)
        {
            if (expression[i] == ')')
            {
                index[stk.top()] = i;
                stk.pop();
            }
            else if (expression[i] == '(')
            {
                stk.push(i);
            }
        }
        return DFS(expression, 1, expression.size() - 2);
    }
    unordered_map<string, vector<int>> scope;

    int evaluate_2(string expression)
    {
        int start = 0;
        return innerEvaluate(expression, start);
    }

    int innerEvaluate(const string &expression, int &start)
    {
        if (expression[start] != '(')
        { // 非表达式，可能为：整数或变量
            if (islower(expression[start]))
            {
                string var = parseVar(expression, start); // 变量
                return scope[var].back();
            }
            else
            { // 整数
                return parseInt(expression, start);
            }
        }
        int ret;
        start++; // 移除左括号
        if (expression[start] == 'l')
        {               // "let" 表达式
            start += 4; // 移除 "let "
            vector<string> vars;
            while (true)
            {
                if (!islower(expression[start]))
                {
                    ret = innerEvaluate(expression, start); // let 表达式的最后一个 expr 表达式的值
                    break;
                }
                string var = parseVar(expression, start);
                if (expression[start] == ')')
                {
                    ret = scope[var].back(); // let 表达式的最后一个 expr 表达式的值
                    break;
                }
                vars.push_back(var);
                start++; // 移除空格
                int e = innerEvaluate(expression, start);
                scope[var].push_back(e);
                start++; // 移除空格
            }
            for (auto var : vars)
            {
                scope[var].pop_back(); // 清除当前作用域的变量
            }
        }
        else if (expression[start] == 'a')
        {               // "add" 表达式
            start += 4; // 移除 "add "
            int e1 = innerEvaluate(expression, start);
            start++; // 移除空格
            int e2 = innerEvaluate(expression, start);
            ret = e1 + e2;
        }
        else
        {               // "mult" 表达式
            start += 5; // 移除 "mult "
            int e1 = innerEvaluate(expression, start);
            start++; // 移除空格
            int e2 = innerEvaluate(expression, start);
            ret = e1 * e2;
        }
        start++; // 移除右括号
        return ret;
    }

    int parseInt(const string &expression, int &start)
    { // 解析整数
        int n = expression.size();
        int ret = 0, sign = 1;
        if (expression[start] == '-')
        {
            sign = -1;
            start++;
        }
        while (start < n && isdigit(expression[start]))
        {
            ret = ret * 10 + (expression[start] - '0');
            start++;
        }
        return sign * ret;
    }

    string parseVar(const string &expression, int &start)
    { // 解析变量
        int n = expression.size();
        string ret;
        while (start < n && expression[start] != ' ' && expression[start] != ')')
        {
            ret.push_back(expression[start]);
            start++;
        }
        return ret;
    }
};
int main()
{
    /**
     * @brief Test case
     * "(let x 1 x)"
    "(mult 4 6)"
    "(add 4 6)"
    "(let x 6 (mult x 6))"
    "(let x 6 (add x 6))"
    "(let x 2 (mult x (let x 3 y 4 (add x y))))"
    "(let var 78 b 77 (let c 33 (add c (mult var 66))))"
    "(add 1 2)"
    "(let x 2 (mult x (let x 3 y 4 (add x y))))"
    "(let x 3 x 2 x)"
    "(let x 1 y 2 x (add x y) (add x y))"
    "(let x 2 (add (let x 3 (let x 4 x)) x))"
    "(let x 7 -12)"
    "(let a (add 1 2) b (mult a 3) c 4 d (add a b) (mult d d))"
        *
     */
    Solution s;
    string exp = "(let x 1 x)";
    cout << s.evaluate(exp) << endl;
    system("pause");
    return 0;
}
